The present invention relates to electronic sorting.
As the state of VLSI technology has continued to provide increased circuit densities, it has become practical to migrate into hardware many data processing functions that have traditionally been implemented in software. Multiplication, array processing, and fast Fourier transform processing are but several examples. In this vein, much interest has arisen in the past few years in the hardware realization of the sorting function, i.e., the rearrangement of a plurality of multi-digit input words or values in accordance with some predetermined criterion, such as numerical order. Indeed, hardware implementation of many of the standard sorting techniques have been proposed. A number of these arrangements are described, for example, in C. D. Thompson, "The VLSI Complexity of Sorting," Memorandum No. UCB/ERL M82/5, Electronics Research Laboratory, College of Engineering, University of California, Berkeley, Feb. 14, 1982. A disadvantage of most of the known sorting techniques is that in addition to the time required for input/output (I/O), a substantial amount of processing time is required to perform the sort itself. The arrangement described by Thompson, for example, require anywhere from N to (N lg.sup.3 N) processing cycles to perform the sort, where N is the number of values being sorted. At least one arrangement is known which may require very little, if any, sort processing time. See, for example, U.S. Pat. No. 4,030,077 issued June 14, 1977 to J. K. Florence et al. That arrangement, however, requires a substantial amount of circuitry to do the job.